package datastructure.book.dp._1_pathway.all;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class _8_Solution {
    int[][][] f;
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        f = new int[m][n][maxMove+1];
        for (int[][] ints : f) {
            for (int[] anInt : ints) {
                Arrays.fill(anInt,-1);
            }
        }
        return findPaths0(m,n,maxMove,startRow,startColumn);
    }

    private int findPaths0(int m, int n, int maxMove, int startRow, int startColumn) {
        if (maxMove < 1) {
            return 0;
        }
        if (f[startRow][startColumn][maxMove] != -1){
            return f[startRow][startColumn][maxMove];
        }
        boolean up = true;
        boolean down = true;
        boolean left = true;
        boolean right = true;
        if (startRow - 1 < 0) {
            up = false;
        }
        if (startColumn - 1 < 0) {
            left = false;
        }
        if (startRow + 1 > m-1) {
            down = false;
        }
        if (startColumn + 1 > n-1) {
            right = false;
        }
        if (f[startRow][startColumn][1] == -1) {
            f[startRow][startColumn][1] = 0;
            if (!up) {
                f[startRow][startColumn][1]++;
            }
            if (!left) {
                f[startRow][startColumn][1]++;
            }
            if (!down) {
                f[startRow][startColumn][1]++;
            }
            if (!right) {
                f[startRow][startColumn][1]++;
            }
        }
        if (maxMove == 1){
            return f[startRow][startColumn][1];
        }else {
            f[startRow][startColumn][maxMove] = 0;
            f[startRow][startColumn][maxMove] += f[startRow][startColumn][1];
        }
        if (up) {
            if (f[startRow - 1][startColumn][maxMove - 1] != -1) {
                f[startRow][startColumn][maxMove] += f[startRow - 1][startColumn][maxMove - 1];
            } else {
                f[startRow][startColumn][maxMove] += findPaths0(m,n,maxMove-1,startRow - 1,startColumn);
            }
            f[startRow][startColumn][maxMove]%=1000000007;
        }
        if (left) {
            if (f[startRow][startColumn - 1][maxMove - 1] != -1) {
                f[startRow][startColumn][maxMove] += f[startRow][startColumn - 1][maxMove - 1];
            } else {
                f[startRow][startColumn][maxMove] += findPaths0(m,n,maxMove-1,startRow,startColumn - 1);
            }
            f[startRow][startColumn][maxMove]%=1000000007;
        }
        if (down) {
            if (f[startRow+1][startColumn][maxMove - 1] != -1) {
                f[startRow][startColumn][maxMove] += f[startRow+1][startColumn][maxMove - 1];
            } else {
                f[startRow][startColumn][maxMove] += findPaths0(m,n,maxMove-1,startRow+1,startColumn);
            }
            f[startRow][startColumn][maxMove]%=1000000007;
        }
        if (right) {
            if (f[startRow][startColumn+1][maxMove - 1] != -1) {
                f[startRow][startColumn][maxMove] += f[startRow][startColumn+1][maxMove-1];
            } else {
                f[startRow][startColumn][maxMove] += findPaths0(m,n,maxMove-1,startRow,startColumn+1);
            }
            f[startRow][startColumn][maxMove]%=1000000007;
        }
        return f[startRow][startColumn][maxMove];
    }

    @Test
    public void testFindPaths(){
        int m = 3;int n = 2;int maxMove = 5;int startRow = 1; int startColumn = 1;
        System.out.println(findPaths(m, n, maxMove, startRow, startColumn));
    }
}
